"""
创建了虚拟头节点
"""


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 1. 特殊情况
        if not head:
            return head
        dummy = ListNode(0)

        dummy.next = head
        slow = dummy
        fast = dummy

        for i in range(n):
            fast = fast.next

        while True:
            if fast and not fast.next:
                slow.next = slow.next.next
                return dummy.next
            else:
                slow = slow.next
                fast = fast.next


#############################
"""
特殊情况：链表为空，直接返回none
首先，双指针，指针fast、slow均初始化为head
然后，让fast先走n步(由于n肯定不会超过链表长度)
    此时，如果fast为空，表明需要删除头结点，直接返回head.next
    此时，如果fast存在，表明粗腰删除中间节点，进行下需操作
接下来，slow和fast同步走，当fast变成最后一个节点时，slow.next = slow.next.next，并返回head

"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head is None:
            return None
        
        slow, fast = head, head

        for _ in range(n):
            fast = fast.next
        if fast is None:
            return head.next
         
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head